{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Introduction aux graphes\n", "\n", "Dans ce TP, on va apprendre ce que sont les graphes.\n", "\n", "Pour tracer des graphes en Python, on peut utiliser la librairie `networkx`. Essayez de relancer le code plusieurs fois pour voir comment le graphe est affiché." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exemples et premières définitions" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt \n", "import networkx as nx\n", "\n", "# un exemple de graphe un peu compliqué\n", "nx.draw(nx.hypercube_graph(3))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Que constatez-vous en lançant la fonction deux fois d'affilée ? Selon vous, est-ce que ces deux graphes sont les mêmes ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "De façon générale, on peut représenter un graphe par deux ensembles :\n", "\n", "* un ensemble de points : les **sommets** ;\n", "* un ensemble de liaison entre les sommets : les **arêtes**.\n", "\n", "C'est une façon abstraite de représenter des liens entre des objets, et on verra que cela peut permettre de représenter beaucoup de choses différentes, et cela permet de raisonner dessus pour résoudre des problèmes plus ou moins compliqués.\n", "\n", "Regardons un autre exemple, cette fois on va le définir nous-mêmes." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# définir un graphe vide\n", "G = nx.Graph()\n", "\n", "# sommets et aretes\n", "sommets = [1, 2, 3, 4]\n", "aretes = [(1,2), (2,3), (2,4), (4,1), (1,3)]\n", "\n", "# rajouter des sommets\n", "G.add_nodes_from(sommets)\n", "\n", "# rajouter des arêtes\n", "G.add_edges_from(aretes)\n", "\n", "# afficher le graphe\n", "nx.draw(G)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice.** Essayez de tracer le cube d'au dessus en définissant vous-mêmes le cube d'au dessus. (Vous pouvez commencer par le dessiner sur papier pour voir quelles sont les arêtes à rajouter.)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# définir un graphe vide\n", "G_cube = nx.Graph()\n", "\n", "# sommets\n", "sommets_cube = [1, 2, 3, 4, 5, 6, 7, 8]\n", "\n", "# aretes (A COMPLETER)\n", "aretes_cube = []\n", "\n", "# il y a 8 sommets dans le cube\n", "G_cube.add_nodes_from(sommets_cube)\n", "\n", "# à vous de rajouter les bonnes arêtes !\n", "G_cube.add_edges_from(aretes_cube)\n", "\n", "# afficher le graphe (l'argument `with_labels` permet d'afficher les noms des sommets)\n", "nx.draw(G_cube, with_labels=True, node_color=\"lightblue\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice bonus.** (Si vous vous ennuyez à la fin.) On appelle *hypercube* un cube dans un espace de dimension *n*. Par exemple, en dimension 1, cela donne une ligne, en dimension 2, un carré, et en dimension 3, un cube. On passe d'un hypercube de dimension *n* à un hypercube de dimension *n+1* en dupliquant l'hypercube de dimension *n*, et en reliant les sommets qui ont le même numéro de chaque cube ensemble.\n", "\n", "Si vous avez le temps à la fin, essayez de définir une fonction qui affiche un hyper cube de dimension *n*." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Quand les sommets ont un nom (ici un numéro), on parle d'**étiquette**, et on dit que le graphe est **étiqueté**. Les étiquettes ne sont pas nécessairement des chiffres, ça peut par exemple être des noms de villes !\n", "\n", "Par exemple, si l'on prend quelques grandes villes françaises, on peut avoir ce graphe :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "G_villes = nx.Graph()\n", "\n", "villes = [\"Lille\", \"Paris\", \"Lyon\", \"Marseille\", \"Nantes\", \"Rennes\", \"Toulouse\"]\n", "aretes_villes = [(\"Lille\", \"Paris\"),\n", " (\"Paris\", \"Lyon\"),\n", " (\"Paris\", \"Nantes\"),\n", " (\"Paris\", \"Rennes\"),\n", " (\"Paris\", \"Toulouse\"),\n", " (\"Lyon\", \"Marseille\"),\n", " (\"Nantes\", \"Rennes\")]\n", "\n", "G_villes.add_nodes_from(villes)\n", "G_villes.add_edges_from(aretes_villes)\n", "\n", "nx.draw(G_villes, with_labels=True, node_color=\"lightblue\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graphes pondérés" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut se dire ici que les arêtes représentent les grands axes routiers. Mais toutes les villes ne sont pas à la même distance les unes des autres...\n", "\n", "Bien sûr, il est possible d'encoder ces informations sur le graphe ! On rajoute donc un poids sur les arêtes, et on parle de **graphe pondéré**." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "G_villes_pondere = nx.Graph()\n", "\n", "# les distances entre chacune des villes\n", "aretes_villes_poids = {(\"Lille\", \"Paris\"): 205,\n", " (\"Paris\", \"Lyon\"): 393,\n", " (\"Paris\", \"Nantes\"): 343,\n", " (\"Paris\", \"Rennes\"): 309,\n", " (\"Paris\", \"Toulouse\"): 586,\n", " (\"Lyon\", \"Marseille\"): 276,\n", " (\"Nantes\", \"Rennes\"): 98}\n", "\n", "# ajouter les sommets et arêtes\n", "G_villes_pondere.add_nodes_from(villes)\n", "G_villes_pondere.add_edges_from(aretes_villes_poids)\n", "\n", "# on va afficher d'abord les noeuds, puis les arêtes\n", "# pour pouvoir faire ça, il faut d'abord définir la position des sommets du graphe\n", "pos = nx.spring_layout(G_villes_pondere) \n", "nx.draw(G_villes, pos, with_labels=True, node_color=\"lightblue\")\n", "nx.draw_networkx_edge_labels(G_villes_pondere, pos, edge_labels=aretes_villes_poids);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Chemins dans un graphe" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut se demander comment faire pour aller d'une ville à une autre. \n", "\n", "Dans ce cas, on considère qu'on peut se déplacer d'un sommet à un autre s'il existe une arête entre les deux. S'il existe une séquence de sommets $(S_1,\\dots,S_k)$ avec des arêtes entre deux sommets consécutifs (entre $S_1$ et $S_2$, $S_2$ et $S_3$, etc.), on dit que cette séquence de sommets est un **chemin**.\n", "\n", "Il existe des algorithmes qui permettent de trouver des chemins dans un graphe, soit entre deux sommets, soit entre toutes les paires de sommets, soit d'un sommet à tous les autres.\n", "\n", "Pour l'instant, on ne va pas trop s'intéresser au fonctionnement de l'algorithme qui permet de trouver des chemins, on verra ça bientôt... mais regardons quand même par où on doit passer pour aller voir le soleil !" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# un algorithme tout fait qui permet de trouver le chemin le plus court dans le graphe\n", "court_chemin = nx.shortest_path(G_villes, \"Lille\", \"Marseille\", weight=\"weight\")\n", "\n", "# des couleurs pour afficher le chemin\n", "couleurs = [\"red\" if sommet in court_chemin else \"lightblue\" for sommet in villes]\n", "\n", "# affichage du graphe\n", "nx.draw(G_villes_pondere, pos, with_labels=True)\n", "nx.draw_networkx_edge_labels(G_villes_pondere, pos, edge_labels=aretes_villes_poids)\n", "nx.draw_networkx_nodes(G_villes_pondere, pos, node_color=couleurs)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Prenons maintenant un graphe avec un petit peu plus de villes :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# charger le graphe depuis un fichier\n", "G_grand = nx.read_gml(\"villes.gml\")\n", "\n", "\n", "# position et poids du graphe\n", "pos_grand = {u: (p[\"x\"], p[\"y\"]) for u, p in G_grand.nodes(data=True)}\n", "aretes_poids_grand = {(u,v,): int(d['weight']) for u, v, d in G_grand.edges(data=True)}\n", "\n", "# affichage du graphe\n", "plt.figure(figsize=(8, 9))\n", "nx.draw(G_grand, pos_grand, node_color=\"lightblue\", with_labels=True)\n", "nx.draw_networkx_edge_labels(G_grand, pos_grand, edge_labels=aretes_poids_grand);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Trouver et afficher le chemin le plus court entre Rennes et Nice." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graphes Orientés" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Parfois, quand on va d'un point à un autre, on ne peut pas revenir en arrière. En terme de graphes, cela signifie que les arêtes, au lieu d'être un simple lien entre deux sommets, ne vont plus que dans un sens.\n", "\n", "Ce type d'arête est représenté par une flèche, et on parle alors de **graphe orienté**.\n", "\n", "Disons que je suis un peu maniaque, et quand je me déplace en France, je n'accepte de parcourir les villes que dans l'ordre alphabétique. Le graphe qui correspond aux chemins que je peux prendre est alors le suivant :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# nouveau graphe orienté\n", "G_oriente = nx.DiGraph()\n", "\n", "aretes_orientees = [(u, v) if u < v else (v, u) for u, v in G_grand.edges()]\n", "\n", "G_oriente.add_nodes_from(G_grand.nodes())\n", "G_oriente.add_edges_from(aretes_orientees)\n", "\n", "# position et poids du graphe\n", "pos_oriente = {u: (p[\"x\"], p[\"y\"]) for u, p in G_grand.nodes(data=True)}\n", "aretes_poids_oriente = {(u,v,): int(d['weight']) for u, v, d in G_grand.edges(data=True)}\n", "\n", "# affichage du graphe\n", "plt.figure(figsize=(12,12))\n", "nx.draw(G_oriente, pos_oriente, node_color=\"lightblue\", with_labels=True)\n", "nx.draw_networkx_edge_labels(G_oriente, pos_oriente, edge_labels=aretes_poids_oriente);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Selon ces règles, quel est le chemin le plus court entre Nice et Toulouse ? Trouvez le et affichez le.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Essayez, comme tout à l'heure, de trouver un chemin entre Rennes et Nice. Que se passe-t-il ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }